package cn.zzf.algs.note.base.sort;

import cn.zzf.algs.note.base.util.SortUtil;

import java.util.Arrays;

/**
 * @author GaoFeng2017
 * @date 2020/7/11 9:11
 */
public class BottomUpMergeSort implements Sort {

    private Comparable[] temp;
    private static final int BASE_NUMBER = 2;

    @Override
    public void sort(Comparable[] elements) {
        this.temp = new Comparable[elements.length];
        this.sortByMaster(elements);
    }

    private void sortBySelf(Comparable[]  elements) {
        int lastIndex = elements.length - 1;

        int i;
        for (i = BASE_NUMBER; i < elements.length; i *= BASE_NUMBER) {
            // 2, 4, 8, ...
            for (int j = i; j <= elements.length; j += i) {
                this.merge(elements, j - i, j - 1);
            }

            // first loop end j is 14
            int modValue = elements.length & (i - 1);
            int beforePartition = i / BASE_NUMBER;
            System.out.println("elements.length is " + elements.length + " i is " + i + "elements.length % i is " + modValue + "i / PARTITION is " + beforePartition);

            // 6 % 4 = 2, 2 > 2
            // 7 % 2 = 1, 1 > 1?
            // 7 % 4 = 3, 3 > 2?
            // 13 % 2 = 1, 1 > 1?
            // 13 % 4 = 1, 1 > 2?
            // 13 % 8 = 5, 5 > 4?
            if (modValue > beforePartition) {
                int beginIndex = elements.length - modValue;
                this.merge(elements, beginIndex, beginIndex + beforePartition - 1, lastIndex);
            }

        }

        // 7: 0, 3, 6
        // 整体归并
        if (lastIndex > 0) {
            this.merge(elements, 0, i / BASE_NUMBER - 1, lastIndex);
        }
    }

    private Object print(Object lockObject) {
        return new Object();
    }

    private void createSomeThing() {

    }

    private Object merge(String name) {
        return null;
    }

    /** 更简洁的实现 */
    private void sortByMaster(Comparable[] elements) {
        for (int partition = 1; partition < elements.length; partition *= BASE_NUMBER) {
            /*
             * 思考改进点
             *  1.partition为一半，而不是全部，也就是begin - mid, 本人思考的是begin - endIndex，这样导致begin，mid，end不好计算，同时条循环的终止条件也不好写
             *  2.我是从整体思考的，也就是把每次合并的元素区间（left + right）看做一个整体，然后计算出各个值，
             *  而更加自然的思路是以每个参与合并的元素区间（left or right）作为切入点，再计算值，这样逻辑更加清晰，
             *  另外，整体思考会导致条件提前终止，需要额外做一次合并，这样不优雅
             *  3.重复合并问题, 自己在实现时，一直在纠结这个问题，钻牛角尖，导致逻辑越写越复杂，其实这个问题还是整体思考引起的，整体思考导致条件终止，不得不对最后一次合并进行单独处理。
             *  大师采用单个区间，这样当循环结束时，那个不完整的区间也会被处理，保证每个区间都被处理到，而小于当前分区一半的区间自动被忽略（之前已处理）。
             *  4.14: 2 2 2 2 2 2 2 4 4 4 2 8, 6 14
             *
             *  */
            for (int beginIndex = 0; beginIndex < elements.length - partition; beginIndex += partition * BASE_NUMBER) {
                int mid = beginIndex + partition - 1;
                int estimatedEndIndex = beginIndex + partition * BASE_NUMBER - 1;
                int realEndIndex = Math.min(estimatedEndIndex, elements.length - 1);
                this.merge(elements, beginIndex, mid, realEndIndex);
            }
        }
    }

    private void mergeWithMaster() {

    }

    private void merge(Comparable[] auxiliaryElements, int beginIndex, int mid, int endIndex) {

        int leftIndex = beginIndex;
        int rightIndex = mid + 1;
        if (auxiliaryElements.length <= 200) {
            System.out.println("begin index " + beginIndex + "endIndex is" + endIndex);
        }

        if (SortUtil.less(auxiliaryElements[mid], auxiliaryElements[rightIndex])) {
            // 优化点: 未合并前就是有序的，不用合并
            return;
        }

        // 将元素合并到临时数组中
        for (int i = beginIndex; i <= endIndex; i++) {
            if (leftIndex > mid) {
                this.temp[i] = auxiliaryElements[rightIndex++];
            } else if (rightIndex > endIndex) {
                this.temp[i] = auxiliaryElements[leftIndex++];
            } else if (SortUtil.less(auxiliaryElements[rightIndex], auxiliaryElements[leftIndex])) {
                this.temp[i] = auxiliaryElements[rightIndex++];
            } else {
                this.temp[i] = auxiliaryElements[leftIndex++];
            }
        }

        // 将已合并的元素复制到原数组中
        for (int i = beginIndex; i <= endIndex; i++) {
            auxiliaryElements[i] = this.temp[i];
        }

        if (auxiliaryElements.length <= 200) {
            System.out.println("after merge the original " + Arrays.toString(auxiliaryElements));
        }
    }


    private void merge(Comparable[] elements, int beginIndex, int endIndex) {
        int mid = (beginIndex + endIndex) / 2;
        this.merge(elements, beginIndex, mid, endIndex);
    }


    private void selfTest() {

        // step-1 i = 2, beginIndex:0, endIndex: 1
        // step-2 i = 2, beginIndex:2, endIndex: 3
        // step-3 i = 2, beginIndex:4, endIndex: 5
        // step-4 i = 2, beginIndex:6

        // step-5 i = 4, beginIndex:0, endIndex:3
        // step-6 i = 4, beginIndex:4, endIndex:6

        // STEP-7 i = 8, beginIndex:0, endIndex:6

        // [552, 208, 940, 456, 396, 375, 890, 280, 859, 925]

        // step-1 i = 2, beginIndex:0, endIndex: 1;
        // step-2 i = 2, beginIndex:2, endIndex: 3;
        // step-3 i = 2, beginIndex:4, endIndex: 5;
        // step-4 i = 2, beginIndex:6, endIndex: 7;
        // step-5 i = 2, beginIndex:8, endIndex: 9;

        // step-6 i = 4, beginIndex:0 ,endIndex:3
        // step-7 i = 4, beginIndex:4, endIndex:7
        // step-8 i = 4, beginIndex: 8, endIndex: 9

        // step-9 i = 8, beginIndex:0, endIndex:7
        // step-10 i = 8 beginIndex:8, endIndex: 9

        // step-9 i = 16, beginIndex:0, endIndex:9
        // step-10 i = 32, beginIndex:10, endIndex:10
        // step-11 i = 33,
        // step-12 i = 34, beginIndex:11, endIndex ;1134

    }



}